1. Field of the Invention
The present invention relates to decoding in a communications receiver, and, more particularly, to iterative decoders generating reliability information.
2. Description of the Related Art
Digital transmission and recording systems convey discrete-time data sequences across channels using analog signals that vary as they pass through different channel media (e.g., wireless channels or magnetic/optical recording media). A primary goal of any such system is to convey information at the fastest possible rate with a minimum number of errors. Accordingly, numerous approaches for error control have been developed to try to minimize and/or correct errors in transmitted signals, as illustrated in U.S. Pat. No. 6,029,264 to Kobayashi et al. and xe2x80x9cError Control Coding, Fundamentals and Applications,xe2x80x9d by S. Lin and D. Costello, Jr., Pages 1-14, Prentice Hall, 1983, both of which are incorporated herein fully by reference.
A data sequence may be defined as comprising, for example, a series of bits represented as analog pulses. The analog pulses either change in amplitude or remain unchanged for each corresponding bit interval, and may either represent the bit itself by an amplitude or represent transitions between bits (e.g., one amplitude represents a transition from xe2x80x9c0xe2x80x9d to xe2x80x9c1xe2x80x9d, while a different amplitude may represent a transition from xe2x80x9c1xe2x80x9d to xe2x80x9c0xe2x80x9d). The data sequence is thus transmitted as a sequence of analog pulses, each with duration (interval) T. The analog pulse is filtered to select a pulse shape that is optimal in some manner for detection (e.g., via square-root raised cosine filtering). A receiver attempts to reconstruct the data sequence from the received sequence of analog pulses.
Despite the somewhat imprecise correlation between the original data sequence and the transmitted data sequence ultimately input to a receiver, the different pulses may be distinguishable from each other by a detector using a well-known technique referred to as xe2x80x9csequence detection. In contrast to detecting a present, or current, bit as a decision based solely on a sampled, received pulse, sequence detection examines a sequence of samples over several received pulses to detect a present bit. Even if the signal is corrupted by noise, the detection of each bit is accomplished by i) sampling at the bit interval T and ii) storing the sample value of each pulse at the sample point. The bit being sampled at time n is referred to herein as the xe2x80x9cpresent samplexe2x80x9d or xe2x80x9cpresent bitxe2x80x9d P(n). By comparing the value of the present sample with the value of the samples immediately preceding the present sample in the data sequence it can be determined if a change in amplitude has occurred. The samples immediately preceding the present sample P(n) are the samples taken at time P(nxe2x88x921), P(nxe2x88x922), P(nxe2x88x923), . . . , P(nxe2x88x92M+1), where M is the channel memory. Channel memory M may be considered to be the number of previous samples that influence the present sample. When the present sample is processed, compared, or otherwise under scrutiny, it is also known as the xe2x80x9cbit of interest.xe2x80x9d
Although sequence detection offers a reasonable method of error control, increasing the overall data rate may cause received pulses to overlap. Pulses may overlap at the point of transmission as each symbol period decreases. Pulses may also overlap due to the channel effect known as dispersion. Since the pulses representing the transmitted bits overlap, the combined pulse, obtained by superposition of the overlapping pulses, results in a signal in which the first pulse and the second pulse are less easily distinguished from one another. This effect is known as inter-symbol interference (ISI). At a receiver, the present sample contains not only the amplitude contribution of the pulse for the bit of interest but also includes the amplitude contribution of the xe2x80x9ctailxe2x80x9d of one or more previous pulses.
A sequence detector is employed to detect and identify transmitted (or, in the case of magnetic recording systems, recorded) sequences of pulses that are more likely to be incorrectly transmitted, using a priori knowledge of noise characteristics and impulse response of the channel. For example, a sequence detector may use a priori knowledge of the dependence of noise samples on previous noise samples, noise power, and/or partial response polynomials representative of the channel. A common noise model is called Additive White Gaussian Noise (AWGN), and a common channel model is the linear time-invariant channel with memory. In addition, if the pulses have short tails, ISI in the bit of interest is limited to a small number of previous samples, since after some time interval a previous pulse will have little or no effect on the value of the present sample. For typical implementations of sequence detectors, it is desirable that the samples of the signal tail be limited to a small, finite number of integer values to reduce the number of comparisons that must be made. Systems utilizing this property are called xe2x80x9cpartial responsexe2x80x9d (PR) systems, and the number of previous samples effecting the pulse of the bit of interest is generally known as the channel memory length.
A maximum-likelihood sequence detector (MLSD) is a sequence detector known in the art and used for an uncoded, linear channel with ISI and AWGN. An MLSD detector comprises a whitened, matched filter (WMF), having an output that is sampled at the Nyquist rate of the input signal, and a Viterbi detector employing a version of the well-known Viterbi algorithm (VA). The sampled output of the WMF is input to the Viterbi detector. The trellis structure of the VA algorithm includes i) a sequence of states and ii) a set of paths through the trellis. The state of the trellis is defined by the ideal values for received bits, and each state typically corresponds to a presently received bit and one or more previously received bits with the number of previously received bits generally equivalent to the length of the channel memory. A path through the trellis is termed an output sequence and defines a sequence of transitions between the states through the trellis, with each path corresponding to a block of possible, or allowed, bits.
The trellis of the VA algorithm describes all possible data sequences that can occur at the output of the channel as a result of the input sequence. A particular path through the trellis is determined from the input samples and reflects the maximum-likelihood data sequence transmitted through the ISI channel. The particular path is determined by comparing the likelihood of traversing each of the paths through the trellis given the input samples. A metric, such as minimum Euclidean distance, between the received samples and ideal symbol values is calculated for each state transition to derive a quantity that reflects a likelihood or transition probability for the input sample making the particular transition to the state (sometimes termed a branch metric). Comparing the likelihood of traversing each of the paths is accomplished by comparing the sum of the branch metrics (sometimes termed the path metric) of each path to determine the path exhibiting the maximum likelihood of occurrence given the input samples. These prior art MLSD detectors are generally not practical, particularly for communication and recording systems. The MLSD detectors are generally not practical because the structure of the MLSD is prohibitively complex to implement when the VA algorithm requires a large number of states in the trellis (i.e., the hardware required to implement all the calculations and comparisons is very complex).
Many PR systems utilize equalization to reduce the residual ISI-caused errors of mis-detection, and possibly reduce the number of states in the trellis used by the VA algorithm. Equalization may typically include amplification of the received signal by an amplifier that has a frequency response based on an estimate of the channel""s frequency response. In some PR systems, a data sequence is reconstructed from the received signal after equalization using the Viterbi detector. The noiseless equalizer output sample resulting from the use of this approach is affected by only a finite number of previous input (transmitted or recorded) samples; thus, the set of equalizer output values has fixed boundaries.
The well-known Viterbi algorithm employed by a Viterbi detector is relatively simple and the optimum choice for use in an uncoded communication system where soft-output (i.e., a soft decision for a sample and relative reliability of the decision, or other form of reliability-checking) is not required. However, in many applications, the data transmitted over channels is encoded to improve the overall error performance of the system. Soft-output is generated in two common systems. One common system is a concatenated encoding system having a pair of codes (an inner code and an outer code) in which the soft output from decoding of the inner code is employed to improve the performance of the outer code. Another common system is an iterative decoding system in which a decoder xe2x80x9cpurifiesxe2x80x9d its decisions about certain code symbols through repeating a series of operations performed on a whole codeword (i.e., after each iteration there are fewer errors in the code word).
One of the most common algorithms for sequence detection with soft output is Hagenauer""s soft-output-Viterbi-algorithm (SOVA) used in concatenated encoding with an outer code, such as a Reed-Solomon code. The soft output at a particular time instant, produced by the SOVA algorithm, is determined on the basis of the Euclidean distance between the two xe2x80x9cbestxe2x80x9d paths through a trellis that merge to the same state. This merging of states is based on the well-known concept of the xe2x80x9cchannel trellisxe2x80x9d described for MLSD detectors. Two paths are considered merged when the paths converge at some state in the trellis and follow the same sequence of states through the remainder of the trellis.
The merged paths are then compared and a smaller level of reliability (i.e., a lower level of confidence in the accuracy of the data sequence being considered) is assigned to bits that do not agree. The procedure is repeated for all channel (or trellis) states. The VA algorithm""s decision for a particular bit in a sequence together with the bit""s reliability level is referred to as soft output or soft information. According to the SOVA algorithm of the prior art, the comparison is performed for all possible merged path pairs, and for all states. An equivalent comparison defines and compares all possible error event sequences to determine the sequence of bits and corresponding levels of reliability.
A data sequence {aik)} is encoded into a sequence {d(k)} in such a way that sequence {a(k)} can be uniquely reconstructed from sequence {d(k)} to minimize transmission errors, for example, by adding parity bits as an outer code. As used herein, the notation {a(k)}, for example, is used to indicate a sequence a of sample values or bits considered up to discrete time k (i.e., {a(k)} is the sequence a(k,), a(kxe2x88x921), a(kxe2x88x922), . . . , a(kxe2x88x92L)). Using control codes, sequence {a(k)} may be reconstructed even when some symbols of the encoded sequence {d(k)} are corrupted by errors during the transmission of the signal. The Viterbi detector generates a sequence of bit estimates x(k) for the sequence {d(k)} from an input sample sequence {r(k)}. Typically, encoding is performed on a block by block basis, so the decoder will use a corresponding portion (block) of the sequence of bit estimates x(k) output from the Viterbi detector, as well as knowledge of the bit reliabilities of the bit estimates x(k), to decode and error correct. When decoding on a block by block basis, some Viterbi detectors use a trellis that accounts for overlap of samples between blocks. The Viterbi estimate x(k) together with its reliability is generally termed a soft decision.
Due to noise and other disturbances, the block of estimates {x(k)} of the transmitted stream and the transmitted stream itself {d(k)} may differ. Their difference is termed an error sequence {xcex5(k)}, where {xcex5(k)}=(x(k)xe2x88x92d(k)). For good channels that add low noise power and introduce a small number of errors, the error sequence contains a zero in almost each element position, but when the error sequence is nonzero, some error patterns occur much more often than others do. Although any error sequence is possible, these more frequent error patterns tend to dominate overall system performance (e.g., bit error rate (BER)). A recognition and explanation of the phenomenon of recurring error sequences, which is inherent for all PR systems, may be found in xe2x80x9cMaximum Likelihood Sequence Estimators: a Geometric Viewxe2x80x9d by L. Barbosa, IEEE Trans. Inform. Theory, vol. 35, pp. 419-427, March 1989, incorporated fully herein by reference.
The Euclidean distance from channel output sequences corresponding to a sequence {d(k))}, to the channel output sequence corresponding to{d(k)xe2x88x92xcex5(k)}, where {xcex5(k)} is a sequence of one of the dominant (more frequently occurring) error patterns, is always smaller than the distance to any other error sequence. Consequently, the Viterbi detector (which in fact uses Euclidean distance as a metric) confuses sequences that produce the dominant error pattern. Consequently, error sequences causing dominant error patterns are also called minimum distance error event sequences.
A method of finding dominant error event sequences is described in xe2x80x9cError-Event Characterization on Partial-Response Channelsxe2x80x9d by S. Altekar. M. Berggren, B. Moision, P. Siegel, and J. Wolf, IEEE Trans. Inform. Theory, vol. 45, no. 1, pp. 241-247, January 1999, incorporated fully herein by reference. In recording systems, for a given partial response polynomial, the set of dominant error event sequences depends also on the channel bit density (e.g., the number of pulses transmitted per bit interval) because of noise coloration from equalization. Other methods for determining dominant error event sequences are also known and described in, for example, xe2x80x9cApplication of Partial Response Channel Coding to Magnetic Recording Systemsxe2x80x9d by H. Kobayashi and D. Tang, IBM J. Res. And Dev., vol. 14, pp. 368-375, July 1979 and xe2x80x9cFinite-state Modulation Codes for Data Storagexe2x80x9d by B. Marcus, P. Siegel, and J. Wolf, IEEE Journal on Select. Areas in Cornmun., vol. 10, no. 1, pp5-37, January 1992, both of which are incorporated herein by reference. However, these, prior art systems require that previous samples in a data sequence as well as future samples be considered when evaluating the accuracy of the present sample. This results in a slow and complex procedure that requires considerable system memory to store each and every sample and considerable delay from processing required to generate each decision.
The present invention relates to an iterative decoding system for partial response (PR) channels having inter-symbol interference (ISI) that i) extracts error event likelihoods that are converted to bit reliabilities for estimates from a data sequence transmitted through the PR channel, ii) recalculates the bit reliabilities during a decoding iteration, and iii) updates the error event likelihoods. Updated error event likelihoods are subsequently converted to new bit reliabilities for the next iteration. The estimates correspond to a data sequence having a correlation among the bits of the sequence, and the iterative decoding system has a priori knowledge of typical error events that may occur when generating estimates from the data sequence by, for example, Viterbi detection. For the first iteration of decoding, error event likelihoods are generated from the estimates, received samples corresponding to the estimates, and the a priori knowledge of typical error events. These error event likelihoods are converted into bit reliabilities that, together with estimates for the transmitted bits, are subsequently used by the iterative decoder to decode the estimates. After decoding, the bit estimates are recalculated using the knowledge of the relation between bits of the sequence. The bit reliabilities may then be modified for a subsequent iteration of decoding by increasing those bit reliabilities that tend to show increasing confidence for corresponding decoded bits (i.e., corresponding Viterbi decisions) between iterations, while decreasing those reliabilities that tend to show decreasing confidence for corresponding decoded bits. This modification may be achieved through updating the error event likelihoods using the recalculated bit reliabilities. Such improvements tend to drive the iterative decoding scheme to fewer iterations while maintaining a predetermined probability of error.
In accordance with an exemplary embodiment of the present invention, a sample sequence representing encoded data and filtered by a channel polynomial is iteratively decoded by generating bit estimates for the sample sequence corresponding to the encoded data and extracting error event likelihoods for the bit estimates based on i) the sample sequence, ii) the bit estimates, and iii) an error event list. During a first iteration, the bit estimates are decoded by (1) converting the error event likelihoods into bit reliabilities, (2) decoding the bit estimates into decoded data based on the bit reliabilities, and (3) updating the bit reliabilities based on the decoded data, During a subsequent iteration, the bit estimates are decoded by (1) updating the error event likelihoods based on the updated bit reliabilities; (2) converting the updated error event likelihoods to new bit reliabilities, and (3) decoding the bit estimates into newly decoded data based on the new bit reliabilities.